package Leetcode第一期;

import java.util.*;

/**
 * @author : K k
 * @date : 12:28 2020/9/11
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * <p>
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 
 * <p>
 * 示例:
 * <p>
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 */
public class 字符串的排列_38 {
    List<String> res = new LinkedList<>();
    char[] c;

    public String[] permutation(String s) {
        c = s.toCharArray();
        dfsSovler(0);
        return res.toArray(new String[res.size()]);
    }

    private void dfsSovler(int start) {
        if (start==c.length){
            res.add(String.valueOf(c));
            //到达数组尾部
            return;
        }
        HashSet<Character> set = new HashSet<>(); //每一层对应一个set 用来保证字符依次使用到
        for (int i=start;i<c.length;i++){
            if (set.contains(c[i])) {continue;}//剪枝
            set.add(c[i]);
            swap(i,start);
            dfsSovler(start+1);
            swap(i,start);
        }

    }

    private void swap(int i, int j) {
        //交换值
        char tmp=c[i];
        c[i]=c[j];
        c[j]=tmp;
    }

    public static void main(String[] args) {
        String[] abcs = new 字符串的排列_38().permutation("abc");
        for (String s :
                abcs) {
            System.out.print(s+" ");
        }
    }


}
